﻿/*题目：环形链表的约瑟夫问题
描述:
编号为 1 到 n 的 n 个人围成一圈。从编号为 1 的人开始报数，报到 m 的人离开。
下一个人继续从 1 开始报数。
n-1 轮结束以后，只剩下一个人，问最后留下的这个人编号是多少？

数据范围：1≤𝑛,𝑚≤10000
进阶：空间复杂度 𝑂(1)，时间复杂度 𝑂(𝑛)*/
#define  _CRT_SECURE_NO_WARNINGS
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 *
 * @param n int整型
 * @param m int整型
 * @return int整型
 */
typedef struct ListNode LTNode;
LTNode* LTBuyNode(int x)
{
    LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
    if (!newnode)
    {
        exit(1);
    }
    newnode->val = x;
    newnode->next = NULL;
    return newnode;
}
LTNode* creatCircle(int n)
{
    LTNode* phead = LTBuyNode(1);
    LTNode* ptail = phead;
    for (int i = 2; i < n + 1; i++)
    {
        ptail->next = LTBuyNode(i);
        ptail = ptail->next;
    }
    ptail->next = phead;
    return ptail;
}

int ysf(int n, int m) {
    LTNode* prev = creatCircle(n);
    LTNode* pcur = prev->next;
    int count = 1;
    while (pcur->next != pcur)
    {
        if (count == m)
        {
            prev->next = pcur->next;
            free(pcur);
            pcur = prev->next;
            count = 1;
        }
        else
        {
            prev = pcur;
            pcur = pcur->next;
            count++;
        }
    }
    return pcur->val;
}